package src.stack_queue;

import java.util.*;

public class no239 {//滑动窗口最大值

    //利用双端队列手动实现单调队列，队列中存数组下标
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int j = 0;
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        //i 为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
        // 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }
            //2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offer(i);

            if (i >= k - 1) {
                res[j] = nums[deque.peek()];
                j++;
            }
        }
        return res;
    }





    //也可以把单调队列的pop push getMax操作封装成函数，再调用
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int j = 0;
        myQueue myQueue = new myQueue();

        //先将前k的元素放入队列
        for (int i = 0; i < k; i++) {
            myQueue.offer(nums[i]);
        }
        res[j] = myQueue.getMax();
        j++;

        for (int i = k; i < n; i++) {
            //滑动窗口移除最前面的元素，移除判断该元素是否放入队列
            myQueue.poll(nums[i - k]);
            //滑动窗口加入最后面的元素
            myQueue.offer(nums[i]);
            //记录对应的最大值
            res[j] = myQueue.getMax();
            j++;
        }
        return res;
    }

    static class myQueue {
        ArrayDeque<Integer> deque = new ArrayDeque<>();

        //弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
        void poll(int val) {
            if (!deque.isEmpty() && deque.peek() == val) {
                deque.poll();
            }
        }

        //添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
        //保证队列元素单调递减
        void offer(int val) {
            while (!deque.isEmpty() && val > deque.peekLast()) {
                deque.pollLast();
            }
            deque.offer(val);
        }

        int getMax() {
            return deque.peek();  //队列队顶元素始终为最大值
        }

    }


}


